package william.list;

/**
 * @author ZhangShenao
 * @date 2024/3/9
 * @description <a href="https://leetcode.cn/problems/odd-even-linked-list/description/">...</a>
 */
public class Leetcode328_奇偶链表 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 借助哑头节点实现
     * 维护两个哑头节点odd和even,分别记录奇链表和偶链表的头节点
     * 遍历链表,并维护一个计数索引
     * - 如果当前节点的索引为奇数,则追加到odd链表的末尾
     * - 否则为偶数,则追加到even链表的末尾
     * 最后将even链表追加到odd链表的末尾,并返回odd链表的真实头结点
     * <p>
     * 时间复杂度O(N) 需要遍历一次链表
     * 空间复杂度O(1) 只额外申请了两个哑头节点
     */
    public ListNode oddEvenList(ListNode head) {
        //边界条件校验
        if (head == null) {
            return head;
        }
        //维护两个哑头节点odd和even,分别记录奇链表和偶链表的头节点
        ListNode oddHead = new ListNode();
        ListNode odd = oddHead;
        ListNode evenHead = new ListNode();
        ListNode even = evenHead;

        //遍历链表,并维护一个计数索引
        int idx = 1;    //索引从1开始
        while (head != null) {
            if (idx++ % 2 == 1) {    //奇数节点,追加到odd链表末尾
                odd.next = head;
                odd = odd.next;
            } else {
                even.next = head;
                even = even.next;
            }

            head = head.next;
        }

        even.next = null;   //将even链表末尾清空,避免链表成环

        //最后将even链表追加到odd链表的末尾,并返回odd链表的真实头结点
        odd.next = evenHead.next;
        return oddHead.next;
    }
}
